Archive Magazine CD 1995/Archive Magazine CD 1995.iso/discs/pipeline/abacus/p_line/Custom05/ReadMe

Text File | 1995-05-13 | 17KB | 378 lines

%OP%VS4.13 (28-Apr-92), Gerald L Fitton, R4000 5966 9904 9938
%OP%DP0
%OP%IRY
%OP%PL0
%OP%HM0
%OP%FM0
%OP%BM0
%OP%LM4
%OP%PT1
%OP%PDPipeLine
%OP%WC2,1250,44,1748,0,0,0,0
%CO:A,12,72%
%C%Recursion
%C%by Gerald L Fitton
Keywords:
Recursion deref() Fitton

Introduction

Those of you who are following this Custom Function series will have
read the first four articles of this series.  They can be found in the
directories Custom01, Custom02, Custom03 and Custom04.

I have called the custom function language '4ProL' (this is intended to
be short for PipeDream 4 Programming Language).  Designing a new
language such as '4ProL' is always a compromise between:

(a) Including commands which provide the flexibility needed to carry
    out complex or intricate processes quickly and

(b) Inherent constraints which encourage those 'good' programming
    techniques needed to facilitate debugging and program improvements.

The compromise is to learn a set of conventions (a sub set of the
constraints of the language) which encourage 'good' programming and to
aim to write 'well written' programs.  The conventions which I am
recommending in this series have been discussed with and approved of by
Colton Software.

If you write 'good' programs using the set of conventions I recommend
then you will be able to debug and expand your programs easily than if
you use what I call 'bad' programming techniques.

The earlier articles covered the topics Sequence (calling a function
and returning a result), Conditional execution (If), the use of
Parameters and Named variables, Local and Global variables and
Repetition using For - Next loops.

In this article I introduce the concept of Recursion.


My Example

For my example I am going to calculate the value of a mathematical
function which returns the number of ways of selecting, say, a set of
six lottery numbers from forty nine numbers or three committee members
from a short list of ten.  Although somewhat old fashioned these days,
I shall call the function nCr because, in PipeDream and using ASCII, I
find it difficult to use the more modern notation for this function.

The value of nCr(49,6) is given by: (49*48*47*46*45*44)/(6*5*4*3*2*1).

%L%You will notice that there are r (ie 6) numbers on the top
%L%and there are r numbers on the bottom of the fraction.

%L%The numbers on the top start at n (ie 49) and work downwards;
%L%those on the bottom start at r (ie 6) and work downwards.


Using a For - Next Loop

Any program which uses recursion can also be written using either
'For - Next' or 'Repeat - Until' loops.

One method of calculating nCr(49,6) is to work out the top line first,
ie (49*48*47*46*45*44), then work out the bottom line, (6*5*4*3*2*1),
finally dividing the top line by the bottom line.  I don't recommend
that method because, in some cases (but not this case) it tends to lead
to very large numbers which might 'run off the end' of the calculator
(ie overflow).

The alternative method of calculating the value of nCr(n,r) is to start
by calculating n/r.  This is followed by multiplying the answer
produced by (n-1)/(r-1) and then by (n-2)/(r-2) etc r times.  This is
the method I shall use since it avoids generating very large numbers
which have to be divided by each other after calculation.

%L%Load the file [nCr_1] by double clicking on it.
%L%As well as [nCr_1] you will load the custom function file [c_nCr].

Have a look at the construction of the function "binomial_1".  You will
see that, as usual, I have declared my local variable, "current_value"
by naming it before initialising its value to 1.  For the reasons I
explained in an earlier article it is not possible to declare the
"loop_counter" as a local variable.

For the UK Weekly National Lottery (see the directory Lottery01) the
number of possible lines is nCr(49,6) ie n = 49 and r = 6.  Try these
values in [nCr_1] and you'll see that the number of possible
combinations of six numbers from forty nine is nCr(49,6) =  ?   Well?
What is it?

You'll see that I've included a dummy loop (using the loop variable
"loop_counter_2") to slow down the operation so that you can observe
the calculation proceeding in slot B13.


Recurrence relationships

If you look at the expression for nCr(49,6) you will see that
nCr(49,6) = (49/6)nCr(48,5).  In other words we can express the value
of nCr(49,6) in terms of nCr(48,5).  In the same way we could express
nCr(48,5) as (48/5)nCr(47,4) and so on - but not forever!

In mathematics (long before computers) this type of general statement
existed and it is called a recurrence relationship.

For the function nCr the recurrence relationship is:

 nCr(n,r) = (n/r)*nCr(n-1,r-1) for values of r>1.

When r = 1 we have a problem because 1 - 1 = 0 and dividing by 0 is one
of those things that mathematicians (and computers) find difficult!

When r = 1 the value of nCr((n,1) = n.

This leads us to a mathematical statement which we can write in
PipeDream format as:

 if(r>1,nCr(n,r) = (n/r)*nCr(n-1,r-1),n)


Using Recursion

There is a lot of snobbery about recursion.  It is often portrayed as a
programming feature which can be used only by an expert.

Don't you believe it!

There are many useful mathematical functions (such as the nCr function
above) which are capable of simple expression as a recurrence
relationship but which, in explicit form, look overwhelmingly difficult
to understand!  In these cases using recursion makes the program easier
to write and easier to understand.  When a program is easy to
understand then changing (improving or expanding) it is much easier.
In those cases I recommend using recursion.

Where the reasoning behind the use of recursion is obscure I would
suggest that the writer is just showing off!

There is a drawback to using recursion.  I have to confess that
recursion often takes longer to evaluate than the explicit (but more
complicated) version whether you use a spreadsheet or BASIC.


The Recursive Function

Double click on the file [nCr_2].  It uses the custom function
"binomial_2", the second function contained in the file [c_nCr].

As is usual with my tutorials I have included a lot of material within
the custom function which is not essential to its operation but which,
I think, aids the understanding of how it all works.

The recursive call is made in the line which starts
"...set_value(answer,if . . . )".  This line includes a call to the
function "binomial_2",  that is to say the function "binomial_2" calls
itself!  It is this feature of a function calling itself which makes it
recursive.

There is a difference in the arguments of the original function and the
arguments used in the recursive call.  The original function calculates
nCr(n,r) whereas the recursive call calculates nCr(n-1,r-1).

In fact, after stripping out all the non essential parts of the custom
function nCr, what you are left with is a recursive procedure which
expresses the fact that

 nCr(n,r) = (n/r)*nCr(n-1,r-1).

The mathematical equation 'nCr(n,r) = (n/r)*nCr(n-1,r-1)' is a simple
'recurrence relationship'.  Such mathematical functions are often
expressed in BASIC or in spreadsheets as recursive functions just
because the writing of the 'program' is easier to understand and easier
to get right first time.

I have included in the custom function "binomial_2" a block of local
variables 'r_on_entry', 'r_on_exit' and 'entry_or_exit' with the
intention of letting you see the recursive feature in operation.

On entry each (recursive) call to the custom function is executed only
down to the point where it becomes recursive.  I call this 'entering'
the recursive procedure because you can imagine that each time you
reach the point of recursion you enter (go into and through) a gateway
to the next recursion.  When you go through this gateway to the next
inner incarnation of the function PipeDream stores the 'outer' (old)
function and displays (on screen) a new, inner incarnation of the
custom function.  You can see this happening if you observe the value
of the local variable "r_on_entry".  The early part of the function
(down to the point of recursion) is executed recursively for reducing
values of n and r.  During this part of the recursive procedure the
latter part of the recursive function is never executed.

Naturally we can't keep going inwards for ever.  When you set up a
recursive procedure then, like everything in life, it's important to
know when to stop!  In the case of nCr we have to stop the recursive
procedure when the value of r = 1 because the next incarnation would
lead us to try to divide by zero.

We achieve this halt to the recursion by using an if(,,) function.  The
innermost incarnation of "binomial_2" fails to call itself because the
if(r>1,,) ceases to be true.

What happens after the innermost incarnation of "binomial_2" has been
executed?  If I haven't lost you yet then you'll probably realise that
it is the innermost incarnation of "binomial_2" which reaches the
'...result(answer)' line before any of the 'outer' incarnations.

This value is returned to the next incarnation (going outwards) which
then completes its execution down to '...result(answer)'.

Having 'entered' the recursive procedure r times we must 'unwind' it by
using the 'exit' part of the custom function r times.  You can see this
happening by observing the value of the local variable "r_on_exit".

One at a time the values of '...result(answer)' are returned until
every incarnation has been executed.  Finally the last (outermost)
value is returned to the main spreadsheet.

Also you will see that the local variable "entry_or_exit" takes
appropriate values to show which part of the loop is being executed.

So that both the 'entry' and 'exit' procedures can be observed I have
slowed them down by using a couple of dummy For - Next loops.


The Lottery

Although I deal with the lottery in more detail in the Lottery01
directory (on another disc) I would like to use the calculation of the
probability of winning the fixed £10.00 prize as an example of the use
of the obscure deref() function.

The lottery machine selects six balls from the forty nine.  You select
six numbers from the forty nine.  If three of your six numbers match
three of the winning numbers then you've won £10.00.

Let's consider building up our own set of six balls.  We must choose
three balls from the six winning balls.  This gives nCr(6,3) possible
combinations.  We must also choose a further three from the forty six
losers.  The number of different ways of doing this is nCr(46,3).

These two numbers must be multiplied together to give
nCr(6,3)*nCr(46,3).  Whatever this number is it is the number of
different lines (of six) which win £10.00.


DeRef(slotref)

Let me use this calculation to explain something that has puzzled many
people using the same custom function twice within the same slot.

If you use the same custom function twice within the same slot then
you'll get the wrong answer.  By this I mean that if you try to
calculate nCr(6,3)*nCr(43,3) in one slot using this version of
"binomial_2" then you'll find that the answer you get is wrong.  You'll
get (nCr(43,3))^2 instead!

The way around this problem is to use deref() as described below.  I
would classify this as a bug but it is an obscure one with an obscure
work around.  What I have to say applies to all custom functions and
not only recursive functions - we'll use a simple custom function to
demonstrate the effect and the work around.

Double click on the file [Add] and you will load it and two similar
custom function files [c1_Add] and [c2_Add].  Have a look at the two
slots [Add]E2 and [Add]E3.  The only difference is that slot E2 uses
the function you'll find in [c2_Add] and E3 uses a function of the same
name in [c1_Add].  You will appreciate that [c2_Add] gives the correct
answer but that [c1_Add] doesn't.  In fact, what the function in
[c1_Add] does is to add [c1_Add]add_together(C3) to itself.  The answer
is always double the value in [Add]C3!

The only difference between the two custom functions is that in
[c1_Add]A13 you'll find ...result(answer) whereas in [c2_Add]A13 you'll
find that the deref() function is included as ...result(deref(answer)).

I still haven't worked out exactly why I need the deref() but I do
remember Robert Macmillan explaining it to me once!  After he'd
explained it to me he said "You know Gerald, I think that's the first
time I've understood the way deref() works!"  He was referring to an
application which passed an array to the custom function and returned
another array!  Often you need to use deref() in array operations if
you wish to get the correct answer!  More of this another day.

You will find some (very limited) information about the deref()
function in the PipeDream handbook but it won't tell you that you
should use deref() as a matter of course when using custom functions
that might be repeated within the same slot.

Let's have a look at the way in which the slot [Add]E2 is evaluated and
I'll explain my limited understanding of what is going on.  During the
first part of the calculation the custom function [c2_Add] is evaluated
and the value of the local variable 'answer' is stored not in
[c2_Add]B9 but in PipeDream's private workspace.  Without the deref()
function this value in the private workspace would be overwritten when
the custom function is run the second time.


A Double Recursion

For interest only I include a BASIC program on this disc which I wrote
originally in November 1987 called [Needles].  It is based on an
ancient puzzle.  You have to transfer a block of discs from one needle
to another without placing a large disc on top of a smaller disc.  The
BASIC program uses the same recursive procedure, PROCmove, twice within
itself.

If you look at the parameters passed to the recursive parts of the
procedure you'll see that it implies that a block of discs is moved
from needle 1 to the spare needle so that the 'last' disc on needle 1
is uncovered.  After moving this last disc from needle 1 to needle 2
the block of discs is moved from the spare needle on top of the last
disc (now on needle 2).

By defining the procedure as a recursive one we avoid worrying about
the finer detail of moving the block of discs from needle 1 to the
spare needle.  We stop 'entering' the recursion when we have moved the
last disc of the block we want to move.

Now I'm not pretending that this is a simple problem but you might like
to study it as an example of recursion.  If you are able to find a way
of recording the moves as a PipeDream array or spreadsheet then I'd
like to hear from you.


Summary

Let me start by repeating advice about variables from an earlier
article.  There are three categories of variable - local variables,
parameters and global variables.

Parameters are values passed to custom functions as arguments of the
function.  The value of a parameter should not be changed within a
custom function.

Local variables are declared within a custom function using
set_name(,).  They should have no meaning outside the custom function
in which they are used.

What I have called a 'self contained' custom function is one in which
the only variables are parameters and local variables (ie no global
variables).  Such custom functions can be use by anybody from any
calling document (just like anybody can use the square root function)
without knowing why it works.  Furthermore, 4ProL will not get confused
if the same name is used for local variables within different custom
functions which are all 'working simultaneously'.

A recursive custom function must be 'self contained' in the way in
which I have described otherwise different incarnations of the custom
function will get confused about what value to give the variable.

Use the deref() function to 'disconnect' separate evaluations of the
same custom function within a single slot (or array).

You can always convert a recursive function into a for - next or
repeat - until loop.  Generally, if the function is based on a
recurrence relationship then it is easier to write and understand the
custom function if it is written as a recursive function mirroring the
recurrence relationship!

Many would disagree about this 'ease of writing' statement but I
believe that is because they've not had recursive procedures explained
to them as a way of converting a recurrence relationship such as
nCr(n,r) = (n/r)*nCr(n-1,r-1) to a custom function.  I would say,
"First write down your 'recurrence relationship' and then write your
recursive custom function."